#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

/*
 *
 * 一直觉得排列的题目很有趣，终于想通了根据当前排列计算出下一个排列的方法，在这里记录一下。
 * 例如 2, 6, 3, 5, 4, 1 这个排列， 我们想要找到下一个刚好比他大的排列，
 * 于是可以从后往前看 我们先看后两位 4, 1 能否组成更大的排列，答案是不可以，
 * 同理 5, 4, 1也不可以 直到3, 5, 4, 1这个排列，因为 3 < 5，
 * 我们可以通过重新排列这一段数字，来得到下一个排列 因为我们需要使得新的排列尽量小，
 * 所以我们从后往前找第一个比3更大的数字，发现是4 然后，我们调换3和4的位置，
 * 得到4, 5, 3, 1这个数列 因为我们需要使得新生成的数列尽量小，于是我们可以对5, 3, 1进行排序，
 * 可以发现在这个算法中，我们得到的末尾数字一定是倒序排列的，
 * 于是我们只需要把它反转即可 最终，我们得到了4, 1, 3, 5这个数列 完整的数列则是2, 6, 4, 1, 3, 5
 *
 * */


static void print_vector(vector<int> &nums) {

    for (const auto &item : nums) {
        cout << item;
    }

    cout << "\n";
}

//2, 6, 3, 5, 4, 1
//2  6  4  5  3  1
// 2  6  4  1 3 5
//[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

//arr = [1,2,3] 的下一个排列是 [1,3,2] 。
void nextPermutation1(vector<int> &nums) {
    int length = nums.size() - 1;

    //print_vector(nums);
    for (int i = length; i > 0; --i) {
        if (nums[i - 1] < nums[i]) {
            for (int j = length; j > i - 1; --j) {
                if (nums[j] > nums[i - 1]) {
                    swap(nums[j], nums[i - 1]);
                    sort(nums.begin() + i, nums.end());//然后排序后面的
                    //print_vector(nums);
                    i = length + 1;
                }

            }

        }


    }


}


void nextPermutation(vector<int> &nums) {
    int length = nums.size() - 1;

    //print_vector(nums);
    for (int i = length; i > 0; --i) {
        if (nums[i - 1] < nums[i]) {
            for (int j = length; j > i - 1; --j) {
                if (nums[j] > nums[i - 1]) {
                    swap(nums[j], nums[i - 1]);
                    sort(nums.begin() + i, nums.end());//然后排序后面的
                    //print_vector(nums);
                    goto label;
                }

            }

        }

    }

    reverse(nums.begin(), nums.end());
    label:;


}

